Corelab Seminar
2020-2021
Michael Lampis
Grundy distinguishes treewidth from pathwidth
Abstract.
In this talk we are interested in the "price of generality"
associated with the transition from pathwidth to treewidth. Treewidth
and pathwidth are two of the most studied notions in parameterized
complexity, where they are used to provide fixed-parameter tractable
algorithms for a large variety of NP-hard problems. Because treewidth
generalizes pathwidth, some problems which are tractable for pathwidth
should become intractable for treewidth (this is the "price" of the
added generality of treewidth). Which are these problems?
So far, the same question has been posed for many other pairs of
prominent structural parameters, such as treewidth vs. clique-width,
pathwidth vs. tree-depth, and tree-depth vs. vertex cover. For each
such pair, several natural problems are known which give examples of
this complexity transition. The only exception is, to the best of our
knowledge, the transition from pathwidth to treewidth, where
essentially all known problems seem to have the same complexity for
both parameters. Our main goal in this talk is to give the first
natural example of a problem that is FPT parameterized by pathwidth
but W[1]-hard parameterized by treewidth. This problem is Grundy
Coloring, the problem of ordering the vertices of a graph in a way
that maximizes the number of colors used by the greedy First-Fit
Coloring heuristic.
Joint work with Rémy Belmonte, Eun Jung Kim, Valia Mitsou, and Yota
Otachi, in ESA 2020. Full version available at
https://arxiv.org/abs/2008.07425